//
//  main.cpp
//  random4
//
//  Created by chenyh on 2021/2/20.
//

#include <iostream>
/**
 【例 4-6】 设计程序对随机生成的数字进行排序。
 【分析】这道题中我们采用一种最基本的排序算法——冒泡排序和快速排序算法，在 这里我们只给出结果，具体的原理分析放到第 5 章进行讲解。
 */
#include <stdlib.h>
#include <time.h>
using namespace std;
#define MAX 11
/**输入函数*/
void input(int num[])
{
    int i;
    srand((unsigned)time(NULL));
    for (i=1; i<MAX; i++) {
        num[i]=rand()%100;  //生成随机函数
    }
}
/**输出函数*/
void output(int num[])
{
    int i;
    for (i=1; i<MAX; i++) {
        cout<<num[i]<<" ";
        if (0==i%10) {
            cout<<endl;
        }
    }
    cout<<endl;
    
}
/**冒泡排序*/
void sort(int num[])
{
    int i,j,tmp;
    for (int i=1; i<MAX; i++) {
        cout<<"i:"<<i<<endl;
        for (j=1; j<MAX-i; j++) {
            cout<<"i:"<<i<<"j:"<<j<<endl;
           
            if (num[j]>num[j+1]) {
                tmp=num[j];
                num[j]=num[j+1];
                num[j+1]=tmp;
            }
        }
    }
}

//还有一种冒泡排序的实现方式，这种方式效率并没提高，但是却体现了一定的算法设
//计思想，那就是双向冒泡排序，其实现代码如下

#define swap(x,y){int tmp;tmp=x;x=y;y=tmp;}
/**双向冒泡算法*/
void dvsort(int num[],int low,int high)
{
    int i;
    while (low<high) {
        for (i = low; i<high; i++) { //向高位冒泡
            if (num[i]>num[i+1]) {
                swap(num[i],num[i+1]);
            }
        }
        high--;
        for (i=high; i>low; i--) {   //向低位排序
            if (num[i] < num[i-1]) {
                swap(num[i],num[i-1]);
            }
        }
        low++;
    }
}

/**
 下面我们用快速排序算法实现这道题。快速排序也是一种基本的排序算法，但是其实 现原理与冒泡排序完全不同。在通常情况下，快速排序的时间效率很高，所以这是很常用 的一种排序算法。
 */

/**快速排序算法
 所以快速排序的核心思想就是将小的往左“扔”，将大的往右“扔”，只要能实现这个，就与快速排序的思想吻合。从初学者的角度，“小的往左扔大的往右扔”首先能想到的往往是小的往前插，大的往后插。这确实是一个思路，但我们知道，数组是不擅长插入的。这种思路虽然能吻合快速排序的思想，但实现起来就不是“快速”排序，而是“慢速”排序了。所以这种方法是不可行的。于是就有了下面的“舞动算法”。

 1.快排是对冒泡排序的一种改进，在快速排序中，元素的比较和移动是从两端向中间进行的，关键码较大的元素一次就能从前面移动到后面，关键码较小的元素一次就能从后面移动到前面，元素移动距离的较远，从而减少了总的比较次数和移动次数

 2.快速排序是基于分治法设计的，其分治策略是：
 ①、划分：选定一个元素作为轴值，以轴值为基准将整个序列划分为两个子序列。轴值的位置在划分的过程中确定，并且前一个子序列的元素均小于或者等于轴值，后一个子序列的元素大于或者等于轴值

 ②、求解子问题：分别对划分后的每一个子序列递归处理
 ③、合并：由于对子序列的排序是就地进行的，所以合并并不需要执行任何操作
 
 排序方法
 1.选择轴值，一般是选取第一个元素的关键码。有一个快排的最坏情况就是如果待排序元素是正序或者逆序，就会将除轴值以外的元素分到轴值的一边。
 2.划分
 ①、设置划分区间:i=first,j=end
 ②、执行右侧扫描，直到r[j]小于轴值，将r[j]与r[i]交换，i++
 ③、执行左侧扫描，直到r[i]大于轴值，将r[i]与r[j]交换，j–
 ④、重复二到三直到i=j，确定看轴值的所在位置，返回该位置

  

 初始键值序列 　　23 12 35 6 19 50 28

 一次划分后 　　　[19 13 6]    23  [35 50 28]

 分别进行快速排序 [6 13]  19 　　 [28]　 35   [50]

 　　　　　　　　　　6  [13]　　           35

 　　　　　　　　　　　  13　　  28　　      50

 最终结果                6  13  19  23  28  35  50
 */

//对区间【left，right】进行划分
int Partition(int A[],int left,int right)
{
    int temp = A[left];  //存放到临时变量temp
    while (left<right) { //只要left与right不相遇
        while (left < right && A[right] > temp) {
            right--;//反复右移
        }
        A[left]=A[right];
        while (left < right && A[right] <= temp) {
            left++;//反复右移
        }
        A[right]=A[left];
        
    }
    A[left] = temp; //把temp放到right与left相遇的地方
    return left;    //返回相遇下标
}

/**
 快速排序算法当序列中元素的排列比较随机时效率高，但是当序列中元素接近有序时，会达到最坏时间复杂度O（n^2），产生这种情况的主要原因在于主元没有把当前区间划分为两个长度接近的子区间。有什么办法能解决这个问题呢？那就是随机选取主元，这样虽然算法的最坏时间复杂度仍然是O（n^2）（例如，总是选择A[left]为主元），但是对于任意输入数据的期望时间复杂度都能达到O（n*log n），也就是说，不存在一组特定的数据能使这个算法出现最坏情况。
 */
int randPartition(int A[],int left,int right)
{
    //生成【left，right】内的随机元
    int p = (round(1.0*rand()/RAND_MAX) * (right-left)+left);
    swap(A[p], A[left]); //将随机元和数组第一个元素交换
    int temp = A[left];
    while (left<right) { //只要left与right不相遇
        while (left < right && A[right] > temp) {
            right--;//反复右移
        }
        A[left]=A[right];
        while (left < right && A[right] <= temp) {
            left++;//反复右移
        }
        A[right]=A[left];
        
    }
    A[left] = temp; //把temp放到right与left相遇的地方
    return left;
}

//快速排序的递归实现
void quicksort(int A[],int left,int right)
{
    if (left < right) { //当前区间的长度超过1
        //将【left，right】按A[right]一分为2
        int pos = randPartition(A, left, right);
        quicksort(A, left, pos-1);//对左子区间递归进行快速排序
        quicksort(A, pos+1, right);//对右子区间递归进行快速排序
    }
    
}



template <class T>
void quickSort(T data[],int p,int r) {
    //轴值
    int position = 0;
    if (p < r) {
        position = partition<T>(data, p, r);   //返回划界元素的最终位置
        quickSort(data, p, position-1);     //对划分的子序列进行递归操作
        quickSort(data, position+1, r);
    }
}
/**序列划分函数 确定轴值*/
template <class T> int partition(T data[],int p,int r)
{
    T temp = data[r];
    int i = p-1;
    for (int j=p; j<r; j++) {
        if (data[j] < temp) { //发现小于划界元素的键值时
            i+=1;             //交换元素i+1和元素j的值
            exchange<T>(&data[i], &data[j]);
        }
    }
    exchange<T>(&data[i+1], &data[r]);
    return i+1;
}
/**元素交换函数函数*/
template <class T> void exchange(T *a,T *b)
{
    T temp = *a;
    *a = *b;
    *b = temp;
}









/**
 从伪代码的描述中可以看出，插入排序是一种稳定排序算法。在数据及规模不大的情 况下，插入排序算法具有较好的效率。当一个数据集的元素都在其正确的位置上时，进行 插入排序的时间只是对每一个元素与它前一个元素比较的时间，约等于一次遍历所花的时
 间，一趟排序的时间复杂度为 O(n);然而，在普通情况下，如果数据是随机出现的(即数 据的所有排列出现概率相等)，那么 n 个元素中的每个元素会被移动一个线性的距离，所 以在平均情况和最坏情况下，插入排序的时间复杂度是 O(n2)。
 */
template <typename DataType>
void insertSort(DataType D[],int length) {
    DataType key;
    for (int j=2; j<length; j++) {
        key = D[j];                     //将待排序元素 D[j]存入临时变量 key 中
        int i = j-1;
        while (i > 0 && key < D[i]) {   //循环寻找待排序元素的正确位置
            D[i+1] = D[i];              //将大于待排序元素的值向后移位
            i = i-1;                    //将游标变量减 1
        }
        D[i+1] = key;                   //将待排序元素插入 i+1 的位置
    }
}
/**
上述算法中的输入是一个 DataType 类型的数组，DataType 代表任意数据类型，length 表示数组的长度。我们将 D[0]作为哨兵元素，存储待排序元素。我们通过一个完整的实例 来熟悉插入排序的应用。
【例 5-1】 有一个数组{43,35,1,87,99,67,78,100}，编写一个 C++程序实现对该数组的插 入排序，并输出排序后的数组元素。
 1.  {43,35,1,87,99,67,78,100}
 2.   d[0] = d[2] = 1 {{1},43,35,87,99,67,78,100}
 3.   i = 2-1 = 1
 4.   while(i>0&&d[i]>d[0]) d[1] > d[0] -> d[2] = d[1]  i=0   {1,35,43,87 99 67 78 100}
 d3 = d[2]
 d2 = d[1]
 */

void insertSort(int d[],int n)
{
    int i,j;
    for (j=2; j<n; j++) {
        d[0] = d[j];    //
        i = j-1;
        while (i > 0 && d[i] > d[0]) {
            d[i+1] = d[i];
            i--;
        }
    }
    d[i+1] = d[0];

}

/**
 5.1.3 应用实例与分析
 【例 5-2】 编写一个程序，用户输入任意的 10 个整数，用插入排序法对这 10 个数排
 序，并输出排序后的结果。
 */
void insertSort2(int a[],int n)
{
    int key = 0,i=1,j=0;
    while (i < n) {
        key = a[i];//选取待排序的元素
        j = i-1;
        while (j >=0 && key < a[i]) { //判断排序元素与其前面位置的元素大小
            a[j+1] = a[j];//将大于待排序元素的元素往后移位
            j=j-1;
        }
        a[j+1] = key;//将待排序元素放置到第一个小于它的元素后面
        i++;
    }
}


int main(int argc, const char * argv[]) {
    int num[MAX];
    /*
    cout<<"冒泡排序前:"<<endl;
    input(num);
    output(num);
    sort(num);
    cout<<"冒泡排序后:"<<endl;
    output(num);
    */
    /**
     双向冒泡
     num);
    cout<<"冒泡排序前:"<<endl;
    output(num);
    dvsort(num, 1, MAX-1);
    cout<<"冒泡排序后:"<<endl;
    output(num);
     */
    /**快速排序*/
    cout<<"冒泡排序前:"<<endl;
    input(num);
    output(num);
    quickSort(num,0,10);
    cout<<"冒泡排序后:"<<endl;
    output(num);
    return 0;
    return 0;
}
